ARC117 C - Tricolor Pyramid

問題

提出

やったこと

青白赤→012と置換しておく。下の2色から上の色を決める演算を$ @ とおくと、

code:calc

@|0 1 2

-+-----

0|0 2 1

1|2 1 0

2|1 0 2

見知った演算でこれを構成する方法が思いつかなかった。（公式解説はちゃんと加減に剰余で構成しているので、単純に実力不足……）

ので、この$ @ 演算を観察して法則を見つけ出す方向に。

自身が単位元。$ c @ c = c

交換法則は成り立つ。$ c_1 @ c_2 = c_2 @ c_1

結合法則は成り立たない。$ (c_1 @ c_2) @ c_3 \not= c_1 @ (c_2 @ c_3)

同じ値を2回$ @ するともとに戻る。$ (c_1 @ c_2) @ c_2 = c_1

この形の4項の並び順は割と自由。$ (c_1 @ c_2) @ (c_3 @ c_4) = (c_1 @ c_3) @ (c_2 @ c_4)

これを元にシミュレーションしてみる。以下、$ @ は乗算の如く省略

1段目：$ c_1, c_2, c_3, c_4

2段目：$ c_1c_2, c_2c_3, c_3c_4

3段目：$ (c_1c_2) (c_2c_3), (c_2c_3) (c_3c_4)

4段目：$ ((c_1c_2) (c_2c_3))((c_2c_3) (c_3c_4))

4段目を整理すると、

$ ((c_1c_2) (c_2c_3))((c_2c_3) (c_3c_4))

$ =((c_1c_2) (c_2c_2))((c_3c_3) (c_3c_4)) 入れ替え自由

$ =((c_1c_2) c_2)(c_3 (c_3c_4)) 自身が単位元

$ =c_1c_4 2回$ @ で元通り

ということで、4段なら最下段の両端だけ計算すればいいことになる。

1段・2段も最下段の両端といえば両端なので、2^n段なら両端だけ？（サンプルの入力例4もそうなってるね）

ということで8段でもシミュレーションしてみる。

1段目：$ c_1, c_2, c_3, c_4, c_5, c_6, c_7, c_8

4段目：$ c_1c_4, c_2c_5, c_3c_6, c_4c_7, c_5c_8

7段目：$ (c_1c_4)(c_4c_7), (c_2c_5)(c_5c_8)

うまくいかない雰囲気がある。数段増やしてみると、

1段目：$ c_1, c_2, c_3, c_4, c_5, c_6, c_7, c_8, c_9, c_{10}, c_{11}, c_{12}

4段目：$ c_1c_4, c_2c_5, c_3c_6, c_4c_7, c_5c_8, c_6c_9, c_7c_{10}, c_8c_{11}, c_9c_{12}

7段目：$ (c_1c_4)(c_4c_7), (c_2c_5)(c_5c_8), (c_3c_6)(c_6c_9), (c_4c_7)(c_7c_{10}), (c_5c_8)(c_8c_{11}), (c_6c_9)(c_9c_{12})

10段目：$ ((c_1c_4)(c_4c_7))((c_4c_7)(c_7c_{10})), ((c_2c_5)(c_5c_8))((c_5c_8)(c_8c_{11})), ((c_3c_6)(c_6c_9))((c_6c_9)(c_9c_{12}))

10段目を4段でシミュレーションしたときと同じように整理すると、

10段目：$ c_1c_{10}, c_2c_{11}, c_3c_{12}

つまり、10段のときも両端だけ計算すればOK。

ここまでのシミュレーション結果から、なんとなく同じ要領で$ 3^n 段飛ばしで計算していけることがわかる。

→$ n 大きい順に、$ 3^n 段以上残ってるなら一気に$ 3^n 段減らしていく感じで計算していけばOK！

1回の操作で配列が2/3以下にはなるので、全体の計算量は$ O(N) になる。

雑感

初手の構成ミスって鬼のようにシミュレーションすることになってアレだった。